package leetcode100;

import java.util.Scanner;

/**
 * @author shkstart
 * 描述
 * 一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
 * 输入描述：
 * 输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。
 * 输出描述：
 * 所有连续子数组中和最大的值。
 * @create 2022-11-25-18:21
 */
public class Meme5_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=scanner.nextInt();
        }
        int sum = arr[0];
        int max =arr[0];
        for (int i = 1; i < n; i++) {
        //我们要判断的唯一标准是当前下标数字 的前面sum是否大于0，
        //大于0 ， 将sum +  当前数字
        //小于0 ， 直接将sum舍弃，将当前数字作为起点（sum)
        //需要注意的是，这个起点和滑动窗口不一样
        //滑动窗口是一串连续的有一致特征的数字，我们本题在意的是前面的sum是否>0,
        //有没有特征都无所谓，只在意正负

        //就算当前下标数字是负数，和sum相加之后如果能>0,仍然能让sum变大，
            // 所以我们在乎的是的当前数字前面的sum，
        //当前数字与sum相加之后的可以是负数，会在下一次循环的时候被舍弃
            sum = sum+arr[i]>arr[i]?sum+arr[i] : arr[i];
            max = sum>max ? sum:max;
        }
        System.out.println(max);



    }
}
